﻿//第N个泰波那契数(easy): https://leetcode.cn/problems/n-th-tribonacci-number/description/
class Solution {
public:
    int tribonacci(int n) {
        if(n==0)  return 0;
        if(n==1||n==2)    return 1;
        // vector<int> dp(n+1);
        // dp[0]=0,dp[1]=1,dp[2]=1;
        // for(int i=3;i<n+1;i++)
        //     dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        //空间优化
        int a=0,b=1,c=1;
        int d;
        int i=3;
        while(i<=n)
        {
            d=a+b+c;
            a=b;
            b=c;
            c=d;
            i++;
        }
        return d;
    }
};

//面试题08.01.三步问题(easy): class Solution {
public:
    int waysToStep(int n) {
        const int MOD=1e9+7;
        if(n==1||n==2)  return n;
        if(n==3)        return 4;
        vector<int> dp(n+1);
        dp[1]=1,dp[2]=2,dp[3]=4;
        for(int i=4;i<=n;i++)
        {
            dp[i]=( ( (dp[i-1]+dp[i-2]) %MOD) +dp[i-3] )%MOD;
        }
        return dp[n];
    }
};